package com.practice.sequence;

import java.util.Arrays;

public class FixedSum {
	public int[] sumTwoTo0(int[] a) {
		if (a.length < 2) return null;
		Arrays.sort(a);
		
		return sumToNum(a, 0, 0);
	}
	
	/**
	 * From offset to end of array a[], find two numbers that sum up to a
	 * number.
	 * 
	 * @param a
	 * @param offset
	 * @param num
	 * @return
	 */
	private int[] sumToNum(int[] a, int offset, int num) {
		int i = offset;
		int j = a.length - 1;
		
		while (j > i) {
			if (a[i] + a[j] == num) return new int[]{a[i], a[j]};
			if (a[j] > num-a[i]) {
				j--;
			}
			else {
				i++;
			}
		}
		
		return null;
	}
	
	public int[] sumThreeTo0(int[] a) {
		if (a.length < 3) return null;
		Arrays.sort(a);
		
		for (int i=0; i<a.length-2; i++) {
			int[] s = sumToNum(a, i+1, -a[i]);
			if (s != null) return new int[]{a[i], s[0], s[1]};
		}
		
		return null;
	}
	
	public int[] sumFourTo0(int[] a) {
		if (a.length < 4) return null;
		Arrays.sort(a);
		
		for (int i=0; i<a.length-3; i++) {
			for (int j=i+1; j<a.length-2; j++) {
				int[] s = sumToNum(a, j+1, -a[i]-a[j]);
				if (s != null) return new int[]{a[i], a[j], s[0], s[1]};
			}
		}
		
		return null;
	}
}
